1. Field of the Invention
This invention relates generally to reconstructing versions of a file and particularly, to reconstructing versions of a file in-place when data storage space and memory resources are limited.
2. Description of Related Art
Recent developments in portable computing and computing appliances have resulted in a proliferation of small network attached computing devices, including network computers. Network computers (NCs) place many computers with limited storage and memory resources onto the same network. The limited capacity of these computers is mitigated by low cost and the absence of intense computational work to be performed at the NC. Often these NCs are diskless, storing their operating system or other software in non-volatile random access memory (NVRAM) or flash RAM.
Without local storage or attached media devices, NCs must download updates to their operating system or other software from the attached network. Often in this computing environment, the ability of client computers to update their local software is limited by low network bandwidth or server capacity. In addition, many network computers may vie for the same resource. This produces network contention, for example packet collision and token competition on a low bandwidth channel. Multiple clients may also tax the processing power of a single server trying to download software to all of them concurrently. These problems also exists when a software distribution computer (server) distributes software applications, data and/or files to a target computer (client).
Delta file compression at the target computer or NC solves the problems associated with low network bandwidth and limited server capacity. A delta file is the encoding of the output from a differencing method. A differencing method compresses data by taking advantage of the statistical correlation between different versions of the same data sets. In short, differencing methods achieve compression by finding common sequences between two versions of the same data that can be encoded using a copy reference. Differencing methods find and output the changes made between two versions of the same file by locating common sequences to be copied, and by finding unique sequences to be added explicitly.
The differencing method that creates the delta file takes two versions of the file as input, a base file and a version file to be encoded. The method outputs a delta file representing the incremental changes made between versions, as represented below: EQU F.sub.base +F.sub.version =D.sub.(base, version)
Reconstruction requires the base file and a delta file to rebuild a version, as represented below: EQU F.sub.base +D.sub.(base, version) =F.sub.version
These differencing methods can be used to distribute software over a low bandwidth network such as a point-to-point modem link or the Internet. Upon releasing a new version of software, the version is differenced with respect to the previous version. With compact versions, a low bandwidth channel can effectively distribute a new release of dynamically self-updating software in the form of a binary patch.
The encoding of the output from differencing methods reduces the size of the file to be transmitted and consequently the time to perform software updates. However, decompressing delta encoded files using traditional methods requires scratch space at the target computer, such as data storage space (including memory, disk space, tapes, and any other type of data storage medium). Since both the old file version and the new file version are stored at the same time, the amount of required scratch space is two times the amount required to store the next version. This storage space requirement presents a problem as network attached devices often have limited memory and processor resources in order to limit production costs. For clients with limited space, such as network computers, or computers with limited storage for downloading large applications, such as thin clients, there may be insufficient space for this reconstruction process.
Thus, there is a need in the art for an invention that reduces the amount of time and network bandwidth required to transmit versions of files to a computer in a NC, client/server or distributed file system environment without requiring additional memory or disk space on the target computer.